<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<!-- 
	Copyright (C) 2007, 2008, 2009, 2010, 2011. PARP Research Group.
	<http://perception.inf.um.es>
	University of Murcia, Spain.

	This file is part of the QVision library.

	QVision is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as
	published by the Free Software Foundation, version 3 of the License.

	QVision is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with QVision. If not, see <http://www.gnu.org/licenses/>.
-->

<html><head><meta http-equiv="content-Type" content="text/html;charset=UTF-8">
<title>QVision: Qt&#39;s Image, Video and Computer Vision Library</title>
<meta name="title" content="QVision" />
<meta name="dc.title" content="QVision" />
<meta name="url" content="http://perception.inf.um.es/QVision" />
<meta name="author" content="PARP Research Group - http://perception.inf.um.es" />
<meta name="revisit-after" content="30 DAYS"/>
<meta name="robots" content="index,follow"/>
<meta name="classification" content="*">
<meta name="rating" content="Safe For Kids">
<meta name="distribution" content="GLOBAL"/>
<meta name="description" content="Qt's Image, Video and Computer Vision Library"/>
<meta name="page-topic" content="Computer Vision research and prototype programming"/>
<meta name="geo.country" content="ES" />

<!--
Keywords:
By license:		open source, gnu, lgpl, gpl, free
By theme:		computer vision, image processing, robotics, programming, source, development
By usage:		library, toolkit, framework, prototype, application
By programming specs:	object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping
Interoperability with:	Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack
Functionallity:		image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface
Main data-types:	matrix, vector, tensor, quaternion, image, polyline
Video sources:		webcam, camera, stream
Devices:		embedded, desktop computer, laptop, mini-laptop
Authors:		PARP research group. University of Murcia, Spain.
-->

<meta name="keywords" content="augmented reality, sfm, structure from motion, open source, gnu, lgpl, gpl, free, computer vision, image processing, robotics, programming, source, development, library, toolkit, framework, prototype, application, object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping, Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack, image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface, matrix, vector, tensor, quaternion, image, polyline, webcam, camera, stream, embedded, desktop computer, laptop, mini-laptop, University of Murcia, Spain, PARP research group, vision por computador"/>
<meta http-equiv="keywords" content="augmented reality, sfm, structure from motion, open source, gnu, lgpl, gpl, free, computer vision, image processing, robotics, programming, source, development, library, toolkit, framework, prototype, application, object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping, Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack, image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface, matrix, vector, tensor, quaternion, image, polyline, webcam, camera, stream, embedded, desktop computer, laptop, mini-laptop, University of Murcia, Spain, PARP research group, vision por computador"/>
<meta http-equiv="pragma" content="no-cache"/>
<meta http-equiv="title" content="QVision"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="tabs.css" rel="stylesheet" type="text/css" />
<link rel="shortcut icon" href="favicon.ico" />
</head><body>

<table width="100%"><tr>
	<td><a href="http://perception.inf.um.es/"><img src="parp.png" border="0" /> <big>PARP Research Group</big></a></td>
	<td align="right"><a href="http://www.um.es/"><big>Universidad de Murcia</big> <img src="um.png" border="0" /></a></td>
</tr></table>

<hr /><br />

<table width="95%" align="center"><tr><td>

<!-- Generated by Doxygen 1.6.3 -->
<script type="text/javascript"><!--
var searchBox = new SearchBox("searchBox", "search",false,'Search');
--></script>
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
      <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
      <li><a href="modules.html"><span>Modules</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
          <form id="FSearchBox" action="search.php" method="get">
            <img id="MSearchSelect" src="search/search.png" alt=""/>
            <input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S" 
                   onfocus="searchBox.OnSearchFieldFocus(true)" 
                   onblur="searchBox.OnSearchFieldFocus(false)"/>
          </form>
        </div>
      </li>
    </ul>
  </div>
  <div class="tabs">
    <ul>
      <li><a href="files.html"><span>File&nbsp;List</span></a></li>
      <li><a href="globals.html"><span>File&nbsp;Members</span></a></li>
    </ul>
  </div>
<h1>src/qvmath/qvdisjointset.cpp</h1><a href="qvdisjointset_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> *      Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012. PARP Research Group.</span>
<a name="l00003"></a>00003 <span class="comment"> *      &lt;http://perception.inf.um.es&gt;</span>
<a name="l00004"></a>00004 <span class="comment"> *      University of Murcia, Spain.</span>
<a name="l00005"></a>00005 <span class="comment"> *</span>
<a name="l00006"></a>00006 <span class="comment"> *      This file is part of the QVision library.</span>
<a name="l00007"></a>00007 <span class="comment"> *</span>
<a name="l00008"></a>00008 <span class="comment"> *      QVision is free software: you can redistribute it and/or modify</span>
<a name="l00009"></a>00009 <span class="comment"> *      it under the terms of the GNU Lesser General Public License as</span>
<a name="l00010"></a>00010 <span class="comment"> *      published by the Free Software Foundation, version 3 of the License.</span>
<a name="l00011"></a>00011 <span class="comment"> *</span>
<a name="l00012"></a>00012 <span class="comment"> *      QVision is distributed in the hope that it will be useful,</span>
<a name="l00013"></a>00013 <span class="comment"> *      but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00014"></a>00014 <span class="comment"> *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<a name="l00015"></a>00015 <span class="comment"> *      GNU Lesser General Public License for more details.</span>
<a name="l00016"></a>00016 <span class="comment"> *</span>
<a name="l00017"></a>00017 <span class="comment"> *      You should have received a copy of the GNU Lesser General Public</span>
<a name="l00018"></a>00018 <span class="comment"> *      License along with QVision. If not, see &lt;http://www.gnu.org/licenses/&gt;.</span>
<a name="l00019"></a>00019 <span class="comment"> */</span>
<a name="l00020"></a>00020 
<a name="l00024"></a>00024 
<a name="l00025"></a>00025 <span class="preprocessor">#include &lt;<a class="code" href="qvdefines_8h.html" title="File from the QVision library.">qvdefines.h</a>&gt;</span>
<a name="l00026"></a>00026 <span class="preprocessor">#include &lt;QVDisjointSet&gt;</span>
<a name="l00027"></a>00027 
<a name="l00028"></a><a class="code" href="classQVDisjointSet.html#aa5ca745800720b7234d2455e72a3301b">00028</a> <a class="code" href="classQVDisjointSet.html#aa5ca745800720b7234d2455e72a3301b" title="Constructs a disjoint set.">QVDisjointSet::QVDisjointSet</a>(uInt elements): cols(0), rows(0), elements(elements), parent(elements), rank(elements), count(elements)
<a name="l00029"></a>00029     {
<a name="l00030"></a>00030     Q_ASSERT_X(elements &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of elements equals 0 in constructor&quot;</span>);
<a name="l00031"></a>00031     <span class="comment">//allocData();</span>
<a name="l00032"></a>00032     makeSet();
<a name="l00033"></a>00033     }
<a name="l00034"></a>00034 
<a name="l00035"></a><a class="code" href="classQVDisjointSet.html#a89e21b6bcc9a6e89adea9debf32661ca">00035</a> <a class="code" href="classQVDisjointSet.html#aa5ca745800720b7234d2455e72a3301b" title="Constructs a disjoint set.">QVDisjointSet::QVDisjointSet</a>(<span class="keyword">const</span> <a class="code" href="classQVDisjointSet.html" title="Implementation of a disjoint set data type, based on the union-find algorithm.">QVDisjointSet</a> &amp;other):
<a name="l00036"></a>00036         cols(other.cols),
<a name="l00037"></a>00037         rows(other.rows),
<a name="l00038"></a>00038         elements(other.elements),
<a name="l00039"></a>00039         parent(other.parent),
<a name="l00040"></a>00040         rank(other.rank),
<a name="l00041"></a>00041         count(other.count)
<a name="l00042"></a>00042     {
<a name="l00043"></a>00043     Q_ASSERT_X(elements &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of elements equals 0 in constructor&quot;</span>);
<a name="l00044"></a>00044     <span class="comment">//allocData();</span>
<a name="l00045"></a>00045     <span class="comment">//makeSet();</span>
<a name="l00046"></a>00046     }
<a name="l00047"></a>00047 
<a name="l00048"></a><a class="code" href="classQVDisjointSet.html#a403db4da44d59cbd9088b81b3293ccae">00048</a> <a class="code" href="classQVDisjointSet.html#aa5ca745800720b7234d2455e72a3301b" title="Constructs a disjoint set.">QVDisjointSet::QVDisjointSet</a>(uInt cols, uInt rows): cols(cols), rows(rows), elements(cols*rows)
<a name="l00049"></a>00049     {
<a name="l00050"></a>00050     Q_ASSERT_X(cols &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of columns equals 0 in constructor&quot;</span>);
<a name="l00051"></a>00051     Q_ASSERT_X(rows &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of rows equals 0 in constructor&quot;</span>);
<a name="l00052"></a>00052     <span class="comment">//allocData();</span>
<a name="l00053"></a>00053     makeSet();
<a name="l00054"></a>00054     }
<a name="l00055"></a>00055 
<a name="l00056"></a><a class="code" href="classQVDisjointSet.html#a7af53f9dd45d67e1ee3429582637b5b5">00056</a> <a class="code" href="classQVDisjointSet.html#aa5ca745800720b7234d2455e72a3301b" title="Constructs a disjoint set.">QVDisjointSet::QVDisjointSet</a>(<span class="keyword">const</span> <a class="code" href="classQVGenericImage.html" title="Base class for QVImage objects.">QVGenericImage</a> &amp;image):      cols(image.getCols()), rows(image.getRows()), elements(cols*rows),
<a name="l00057"></a>00057                                                                                                                         parent(elements), rank(elements), count(elements)
<a name="l00058"></a>00058     {
<a name="l00059"></a>00059     Q_ASSERT_X(cols &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of columns equals 0 in constructor&quot;</span>);
<a name="l00060"></a>00060     Q_ASSERT_X(rows &gt; 0, <span class="stringliteral">&quot;QVDisjointSet&quot;</span>, <span class="stringliteral">&quot;Number of rows equals 0 in constructor&quot;</span>);
<a name="l00061"></a>00061     <span class="comment">//allocData();</span>
<a name="l00062"></a>00062     makeSet();
<a name="l00063"></a>00063     }
<a name="l00064"></a>00064 
<a name="l00065"></a>00065 <span class="comment">//QVDisjointSet::~QVDisjointSet()</span>
<a name="l00066"></a>00066 <span class="comment">//    {</span>
<a name="l00067"></a>00067     <span class="comment">//Q_ASSERT_X(parent != 0, &quot;~QVDisjointSet&quot;, &quot;Parent array not allocated&quot;);</span>
<a name="l00068"></a>00068     <span class="comment">//Q_ASSERT_X(rank != 0, &quot;~QVDisjointSet&quot;, &quot;Rank array not allocated&quot;);</span>
<a name="l00069"></a>00069     <span class="comment">//freeData();</span>
<a name="l00070"></a>00070 <span class="comment">//    }</span>
<a name="l00071"></a>00071 
<a name="l00072"></a><a class="code" href="classQVDisjointSet.html#a0da75d74cd958218f3919b4256f7b701">00072</a> uInt <a class="code" href="classQVDisjointSet.html#a092d79e584f33905948f5e812fdb963e" title="Joins two subsets of points.">QVDisjointSet::unify</a>(uInt index1, uInt index2)
<a name="l00073"></a>00073     {
<a name="l00074"></a>00074     Q_ASSERT_X(index1 &lt; elements, <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;First index exceeds number of elements&quot;</span>);
<a name="l00075"></a>00075     Q_ASSERT_X(index2 &lt; elements, <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;Second index exceeds number of elements&quot;</span>);
<a name="l00076"></a>00076 
<a name="l00077"></a>00077     <span class="comment">// Trivial case: elements are the same.</span>
<a name="l00078"></a>00078     <span class="keywordflow">if</span> ( index1 == index2 )
<a name="l00079"></a>00079         <span class="keywordflow">return</span> index1;
<a name="l00080"></a>00080 
<a name="l00081"></a>00081     uInt root1 = <a class="code" href="classQVDisjointSet.html#adb359c333540ac1d8a7e820f799c63be" title="Overloaded version of find, for partitions over the set of points contained in an...">find</a>(index1), root2 = <a class="code" href="classQVDisjointSet.html#adb359c333540ac1d8a7e820f799c63be" title="Overloaded version of find, for partitions over the set of points contained in an...">find</a>(index2);
<a name="l00082"></a>00082 
<a name="l00083"></a>00083     <span class="comment">// Trivial case: elements belong to the same set.</span>
<a name="l00084"></a>00084     <span class="keywordflow">if</span> ( root1 == root2 )
<a name="l00085"></a>00085         <span class="keywordflow">return</span> root1;
<a name="l00086"></a>00086 
<a name="l00087"></a>00087     <span class="comment">// Addon to union-find algorithm to keep count of number of sets with constant cost</span>
<a name="l00088"></a>00088     sets--;
<a name="l00089"></a>00089 
<a name="l00090"></a>00090     Q_ASSERT_X(sets &gt; 0 , <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;Number of sets reached 0&quot;</span>);
<a name="l00091"></a>00091 
<a name="l00092"></a>00092     <span class="keywordflow">if</span> (rank[root1] &gt; rank[root2])
<a name="l00093"></a>00093         {
<a name="l00094"></a>00094         uInt temp = root1;
<a name="l00095"></a>00095         root1 = root2;
<a name="l00096"></a>00096         root2 = temp;
<a name="l00097"></a>00097         }
<a name="l00098"></a>00098 
<a name="l00099"></a>00099     Q_ASSERT_X(rank[root1] == MIN(rank[root1], rank[root2]), <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;first root is minimal&quot;</span>);
<a name="l00100"></a>00100     Q_ASSERT_X(rank[root2] == MAX(rank[root1], rank[root2]), <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;first root is maximal&quot;</span>);
<a name="l00101"></a>00101 
<a name="l00102"></a>00102     <span class="keywordflow">if</span> (rank[root1] == rank[root2])
<a name="l00103"></a>00103         rank[root2] = rank[root2] +1;
<a name="l00104"></a>00104 
<a name="l00105"></a>00105     parent[root1] = root2;
<a name="l00106"></a>00106 
<a name="l00107"></a>00107     <span class="comment">// Addon to union-find algorithm to keep count of cardinality of sets with constant cost</span>
<a name="l00108"></a>00108     count[root2] += count[root1];
<a name="l00109"></a>00109 
<a name="l00110"></a>00110     Q_ASSERT_X(<a class="code" href="classQVDisjointSet.html#adb359c333540ac1d8a7e820f799c63be" title="Overloaded version of find, for partitions over the set of points contained in an...">find</a>(index1) == <a class="code" href="classQVDisjointSet.html#adb359c333540ac1d8a7e820f799c63be" title="Overloaded version of find, for partitions over the set of points contained in an...">find</a>(index2) , <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;Parent for indexes don&#39;t coincide, after unify&quot;</span>);
<a name="l00111"></a>00111     Q_ASSERT_X(root2 == <a class="code" href="classQVDisjointSet.html#adb359c333540ac1d8a7e820f799c63be" title="Overloaded version of find, for partitions over the set of points contained in an...">find</a>(index1) , <span class="stringliteral">&quot;QVDisjointSet::unify&quot;</span>, <span class="stringliteral">&quot;Root2 is not the root for elements.&quot;</span>);
<a name="l00112"></a>00112 
<a name="l00113"></a>00113     <span class="keywordflow">return</span> root2;
<a name="l00114"></a>00114     }
<a name="l00115"></a>00115 
<a name="l00116"></a>00116 <span class="keywordtype">void</span> QVDisjointSet::makeSet()
<a name="l00117"></a>00117     {
<a name="l00118"></a>00118     sets = elements;
<a name="l00119"></a>00119     <span class="keywordflow">for</span> (uInt <a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a> = 0; <a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a> &lt; elements; <a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a>++)
<a name="l00120"></a>00120         {
<a name="l00121"></a>00121         rank[<a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a>] = 0;
<a name="l00122"></a>00122         count[<a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a>] = 1;
<a name="l00123"></a>00123         parent[<a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a>] = <a class="code" href="classQVDisjointSet.html#a1e8ca8f33af020cce71d5d92b9bbcc41" title="Gets the number corresponding to the given point, in the integer set.">index</a>;
<a name="l00124"></a>00124         }
<a name="l00125"></a>00125     }
<a name="l00126"></a>00126 
<a name="l00127"></a>00127 <span class="comment">/*void QVDisjointSet::allocData()</span>
<a name="l00128"></a>00128 <span class="comment">    {</span>
<a name="l00129"></a>00129 <span class="comment">    parent = QVector&lt;uInt&gt;(elements);</span>
<a name="l00130"></a>00130 <span class="comment">    rank = QVector&lt;uInt&gt;(elements);</span>
<a name="l00131"></a>00131 <span class="comment">    count = QVector&lt;uInt&gt;(elements);</span>
<a name="l00132"></a>00132 <span class="comment">    }*/</span>
<a name="l00133"></a>00133 
<a name="l00134"></a>00134 <span class="comment">//void QVDisjointSet::freeData()</span>
<a name="l00135"></a>00135 <span class="comment">//    {</span>
<a name="l00136"></a>00136   <span class="comment">//  delete parent;</span>
<a name="l00137"></a>00137   <span class="comment">//  delete rank;</span>
<a name="l00138"></a>00138   <span class="comment">//  delete count;</span>
<a name="l00139"></a>00139 <span class="comment">//    }</span>
<a name="l00140"></a>00140 
</pre></div></div>
</td></tr></table>

<br /><hr><br />
<center><a href="http://perception.inf.um.es/QVision">QVision framework</a>.
<a href="http://perception.inf.um.es">PARP research group</a>.
Copyright &copy; 2007, 2008, 2009, 2010, 2011.</center>
<br />
</body>
</html>
